#include <climits>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode()
      : val(0), left(nullptr), right(nullptr){} * TreeNode(int x)
      : val(x),
        left(nullptr),
        right(nullptr){} * TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x),
        left(left), right(right) {}
};

TreeNode *buildTree(vector<int> &nums, int left, int right) {
  if (left > right)
    return nullptr;
  int max_idx = -1;
  int max_val = INT_MIN;
  for (int i = left; i <= right; ++i) {
    if (nums[i] >= max_val) {
      max_val = nums[i];
      max_idx = i;
    }
  }
  if (max_idx == -1)
    return nullptr;
  TreeNode *node = new TreeNode(max_val, nullptr, nullptr);
  node->left = buildTree(nums, left, max_idx - 1);
  node->right = buildTree(nums, max_idx + 1, right);
  return node;
}

TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
  return buildTree(nums, 0, nums.size() - 1);
}